package com.study;

/**
 * @program: leetcode
 * @author: jzhou
 * @date: 2022-11-01 21:24
 * @version: 1.0
 * @description: 求x的平方根的整数部分 (求近似解)
 **/
public class SqrtX {

    public static void main(String[] args) {
        System.out.println(binarySearch(63));
        System.out.println(newton(10));
    }

    public static int binarySearch(int x){
        int left = 0,right = x,index = -1;
        while (left <= right){
//            int mid = (left + right) / 2; = left/2 + right/2 =
           int mid = left + (right - left) / 2;
            if (mid * mid > x){
                right = mid - 1;
            }else {
                index = mid;
                left = mid + 1;
            }
        }
        return index;
    }

    /** 15  3 * 5 = 15 两数均值的平方 比 两个数本身的平方更接近于 x
     *  n = x 的平方  =>  (n/x + x) / 2 的结果更趋近于 x
     * 迭代思想 牛顿迭代
     * @param x
     * @return
     */
    public static int newton(int x){
        return (int) sqrt(x,x);
    }

    public static double sqrt(double i,int x){
        double res = (x/i + i)/2; // (16/4 + 4)/2 = 4    (64/8 * 8)/2 = 8
        if (res == i){
            return res;
        }else {
           return sqrt(res,x);
        }
    }

    public static double sqrt1(double i,int x){
        double res = (x/i + i)/2;
        if (res == i){
            return res;
        }
        return sqrt1(res,x);
    }
}
